package regular;

public class MatchString {

    public static void main(String[] args) {
//        System.out.println(new MatchString().isMatch("aa", "a*"));

        System.out.println(new MatchString().isMatch("aasdfasdfasdfasdfas", ".*asdf.*asdf.*asdf.*s"));

    }

    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        //if s and p is empty
        dp[0][0] = true;
        char[] ss = new char[s.length() + 1];
        char[] pp = new char[p.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            ss[i + 1] = s.charAt(i);
        }
        for (int i = 0; i < p.length(); i++) {
            pp[i + 1] = p.charAt(i);
        }


        for (int i = 0; i <= s.length(); i++) {
            for (int j = 0; j <= p.length(); j++) {
                if (j == 0 && i != 0) {
                    dp[i][j] = false;
                }
                if (i == 0 && j != 0) {
                    if (pp[j] == '*') {
                        dp[i][j] = dp[i][j - 2];
                    }
                }
                if (i != 0 && j != 0){
                    if (pp[j] == '*') {
                        dp[i][j] = dp[i][j - 2];
                        if (pp[j - 1] == ss[i] || pp[j - 1] == '.') {
                            dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                        }
                    }
                    if(pp[j] == ss[i] || pp[j] == '.'){
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}
